
#include "main.h"
// 根据带有显式空子节点的先序序列，构建二叉树，将其根节点的地址存入 *root_pp 中
// 初始传入的root_pp的值无任何意义（也即root_pp尚未被正确地初始化，因此需要你来初始化）
// pre_order_seq 指向的字符串类似 "ABC##DE#G##F###"，  其中 # 表示显式的空子节点（空指针域），
// 这一类空子节点并不需要被创建对应的struct Node或者BiTreeNode
char* location;
void scan(char* pre_order_seq) {
    location = pre_order_seq;
}
void create_tree(BiTreeNode** root_pp, char* pre_order_seq, int num_elements) {
    if (*pre_order_seq != '#' && *pre_order_seq != '\0') {
        (*root_pp) = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        (*root_pp)->data = *pre_order_seq;
        num_elements++;
        create_tree(&(*root_pp)->leftChild, (++pre_order_seq), num_elements);
        pre_order_seq = location;
        create_tree(&(*root_pp)->rightChild, (++pre_order_seq), num_elements);
    }
    else if (*pre_order_seq == '\0' || *pre_order_seq == '#') {
        (*root_pp) = NULL;
        scan(pre_order_seq);
        return;
    }
}
void pre_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t != NULL) {
        visit(t->data);
        pre_order_traverse(t->leftChild, visit);
        pre_order_traverse(t->rightChild, visit);
    }
}
void in_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t != NULL) {
        in_order_traverse(t->leftChild, visit);
        visit(t->data);
        in_order_traverse(t->rightChild, visit);
    }

};
void post_order_traverse(BiTreeNode* t, void visit(DataType item)) {
    if (t != NULL) {
        post_order_traverse(t->leftChild, visit);
        post_order_traverse(t->rightChild, visit);
        visit(t->data);
    }
};
int main() {
    BiTreeNode* tre;
    int num_elements = 0;
    char* pre_order_seq = "ABC##DE#G##F###";
    create_tree(&tre, pre_order_seq, num_elements);
    pre_order_traverse(tre, visit);
    printf("\n");
    in_order_traverse(tre, visit);
    printf("\n");
    post_order_traverse(tre, visit);

}